package com.acwing.lc.part1;

import java.util.ArrayList;
import java.util.List;

/**
 * @author rkc
 * @date 2022/9/10 10:58
 */
public class LC22括号生成 {

    private List<String> ans = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        dfs(n, 0, 0, "");
        return ans;
    }

    private void dfs(int n, int lc, int rc, String seq) {
        if (lc == n && rc == n) {
            ans.add(seq);
            return;
        }
        if (lc < n) dfs(n, lc + 1, rc, seq + '(');
        if (rc < n && rc < lc) dfs(n, lc, rc + 1, seq + ')');
    }
}
